Digital transmission systems commonly involve techniques for the detection of digital data represented by a sequence of symbols, where a symbol typically encodes or represents a number of bits. Symbols are transferred as signals through a communications channel, such as a magnetic or optical storage disk channel or a wireless channel. During transfer through a communications channel noise is typically undesirably added to the transmitted signals. In a magnetic recording communications channel, for example, data symbols are written to and stored on a magnetic medium through an encoding process and then read from the magnetic medium through a decoding process. For processing convenience, the encoding and decoding processes operate on blocks of data, each block of data representing a portion of an input data sequence.
Many communications channels can experience a phenomenon known as “burst errors,” where a burst error is generally considered to be a contiguous sequence of symbols being transferred through a communications channel such that the first and last symbols in the sequence are in error. Noise corrupts a transmitted signal representing the sequence of symbols for a period of time equivalent to the period of several encoded or decoded being transmitted. The noise thus results in a group or “burst” of erroneous symbols that undesirably increases the bit error rate (BER) of the communications channel. Furthermore, in communications channels that involve iterative decoding, such as channels utilizing low density parity check (LDPC) codes in the encoding and decoding processes, burst errors can be difficult to correct since such burst errors can happen in a concentrated manner to relatively large numbers of consecutive symbols.
Many communications channels, such as magnetic storage communications channels, interleave encoded data such that the data of respective symbols in a block of data are permuted. Interleaving distributes data so that burst errors affect only a relatively small number of bits in each symbol or group of symbols for which error checking and correction is performed during the encoding and decoding processes. In this way, interleaving the symbols in a block of data prior to transmission of the block through the channel distributes burst errors throughout the deinterleaved block. This enables the erroneous bits in the deinterleaved block to be corrected through error correction utilized in such communications channels.
Nearly all communication channels use some form of error correction coding, which generally involves adding redundant information to a stream of data to enable bit errors that arise during communication to be detected and corrected. Iterative correction codes, such as turbo codes and low-density parity-check (LDPC) codes, are increasingly utilized in many communications channels, such as communications channels for magnetic storage systems. LDPC codes are a class of linear block codes which provide a near capacity performance on a large collection of communications channels, as will be appreciated by those skilled in the art. In a magnetic storage system utilizing LDPC codes, data to be written is encoded to generate a corresponding code word. If the number of erroneous bits within a given code word exceeds the error-correcting capability of the LDPC code, then the original code word and thus the original data cannot be recovered. Interleaving rearranges symbols across several codewords, creating a more uniform distribution of errors such that when deinterleaved erroneous bits are distributed across enough codewords that enable error correction to be performed on respective codewords. Improved interleaving and deinterleaving techniques are desirable.